#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2022/03/07
# @Author   :Changshu
# @File     :Exercise19.py
# 19. 删除链表的倒数第 N 个结点


class ListNode:
	def __init__(self, val=0, next=None):
		self.val = val
		self.next = next

# 1.两次遍历，先确定长度
def removeNthFromEnd1(head: ListNode, n: int) -> ListNode:
	length = 0
	node = head
	while node:
		length += 1
		node = node.next
	if n == length:
		return head.next
	node = head
	for i in range(length - n - 1):
		node = node.next
	node.next = node.next.next
	return head


def removeNthFromEnd2(head: ListNode, n: int) -> ListNode:
	node = head
	fakehead = ListNode(None, head)
	# stack=[fakehead]
	stack = list([fakehead])
	while node:
		stack.append(node)
		node = node.next
	for i in range(n):
		stack.pop()
	rear = stack[-1]
	rear.next = rear.next.next
	return fakehead.next

# def removeNthFromEnd3(head: ListNode, n: int) -> ListNode:

if __name__ == '__main__':
	l=[1,2,3,4,5]
	l.append(6)
	print(l)
	a=l.pop()
	print(a)
	print(l)
	print(l[0])